CD ROM Paradise Collection 4

home *** CD-ROM | disk | FTP | other *** search

/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / hamradio / logic.zip / LOGIC11 / LOGIC.DOC < prev next >

Wrap

Text File | 1995-03-04 | 115KB | 2,337 lines

LOGIC CIRCUIT ANALYSIS Version 1.1, March 1995 Copyright 1991-1995, Arthur Tanzella All Rights Reserved The "Logic Circuit Analysis" program is an educational tool. It introduces the user to logic concepts and digital computers. The user can create and evaluate logic circuits on the computer screen. This documentation or the online tutor functions as a tutorial to learn about logic and digital computers. Numerous sample circuits teach the user how to design and build computer circuits. ACKNOWLEDGEMENTS I would like to thank the following people who are my good friends, and have contributed significantly to this program. Their contributions were in the testing of the program and giving suggestions to make this program and documentation easier to use and read. Warren Cella Mike Weisfield LICENSE AGREEMENT Logic Circuit Analysis is a "Shareware Program" provided at no charge to the user for a one week evaluation period. Feel free to share it with your friends, but please do not give it away altered or as part of another system. The essence of "user-supported" software is to provide users with quality software without high prices, and yet to provide incentive for programmers to continue to develop new products. If you find this program useful and continue to use the program after the one week evaluation period, please make a registration payment of $20 (US) to the following: Arthur Tanzella 4613 Clubvue Drive Pittsburgh, PA 15236-4803 USA To register this program print and fill out the "REGISTER.DOC" file and send it, with the $20 (US) registration fee, to the above address. The $20 (US) registration fee will license one copy for use on one computer at a time. You must treat this software just like a book. As an example, any number of people can use this software if there is no possibility of using it on two computers simultaneously. Treat the software just like a book that cannot be read by two people in two different locations simultaneously. Users of Logic Circuit Analysis must accept this disclaimer of the warranty: "Logic Circuit Analysis" is supplied as is. The author disclaims all warranties, expressed or implied, including, without limitation, the warranties of merchantability and of fitness for any purpose. The author assumes no liability for damages, direct or consequential, which may result from the use of "Logic Circuit Analysis." Commercial users of Logic Circuit Analysis must register and pay for their copies of Logic Circuit Analysis within 30 days of first use or their license is withdrawn. Site-License arrangements are available by contacting Arthur Tanzella at the above address. Anyone distributing Logic Circuit Analysis for any kind of remuneration must first contact Arthur Tanzella at the address above for authorization. This authorization is granted automatically to distributors recognized by the Association of Shareware Professionals (ASP) as adhering to its guidelines for shareware distributors, and such distributors may begin offering Logic Circuit Analysis immediately. However, you must advise Arthur Tanzella so you can be kept up-to-date with the latest version of the Logic Circuit Analysis program. You are encouraged to pass a copy of Logic Circuit Analysis along to your friends for evaluation. Please encourage them to register their copy if they plan to continue using it. All registered users will receive a copy of the latest version of the Logic Circuit Analysis program. Also, registered users will receive a supplementary library of commonly used 7400 series circuits. You could design circuits on the screen using the 7400 series circuits contained in this library. If you have any comments or problems with this program, you can contact me at the address above or send an E-mail message via CompuServe to Arthur Tanzella 71175,76. All registered users will receive support for a minimum of three months from the time they registered. ASP OMBUDSMAN The author is a member of the Association of Shareware Professionals (ASP). The ASP wants to make sure that the shareware principle works for you. If you are unable to resolve a shareware-related problem with an ASP member by contacting the member directly, the ASP can probably help you. The ASP Ombudsman can help you resolve a dispute or problem with an ASP member, but does not provide technical support for members' products. Please write to the ASP Ombudsman at 545 Grover Road, Muskegon, MI 49442 or send an E-mail message via CompuServe to ASP Ombudsman 70007,3536. GETTING STARTED The Logic Circuit Analysis program contains over 100 files occupying approximately 1 MB of disk space and compressed into a single self-extracting file called "INSTALL.EXE." This file was created using the LHarc version 2.11 program, which is a copyright reserved freeware program written by Haruyasu Yoshizaki. To run the program requires an Intel 286 or later microprocessor, an EGA or VGA graphics adapter with 256 KB of RAM installed, and a color monitor. It also requires between 300 KB and 400 KB of available RAM after DOS, drivers and Terminate and Stay Resident (TSR) program are loaded. The actual amount of RAM required depends on the complexity of the circuit. A minimum of 300 KB of RAM is required if Expanded Memory (EMS) is installed. You can use the CHKDSK or MEM command to detect if you have enough available RAM to run this program. Logic Circuit Analysis supports a mouse if installed with either the MOUSE.SYS or MOUSE.COM driver. However, a mouse is not required. The left mouse button is equivalent to the ENTER key and used to select items. The right mouse button is equivalent to the ESC key and used to exit screens. If the mouse has three buttons, the middle button is used in the Modify Circuit screen to display the Library of Components screen, and to switch pages of library components. To start the Logic Circuit Analysis you must be in the directory containing this program. The program is usually stored in the C:\LOGIC11 directory. Use the DOS "CD" (Change Directory) command to change the default directory to the program directory as follows: CD \LOGIC11 To start the program type "LOGIC" with or without parameters as follows: LOGIC or LOGIC filename.LG or LOGIC filename.LG x The program will display the online tutor when no parameters are after the "LOGIC" command. This tutorial contains all the information in this document, and allows access in a Hyper-Text like fashion. The cursor keys (or mouse) can be used to highlight keywords on the screen. The ENTER key will display another screen of information whose subject corresponds to the selected keyword. The PGDN key, or selecting the "More" keyword, will display the next screen of information. The PGUP key will display the previous screen. The F1 key will display the first screen of the tutorial. From the first screen the "Table of Contents" keyword will display a screen containing the Table of Contents that will allow you to jump directly to the desired section. The "Index" keyword will display a screen containing many different keywords. The ESC key will exit the Tutorial and return you to the Logic Circuit Analysis program. The F5 key will allow you to return to the tutorial at the same screen previously displayed. Select Sample Circuit Menu To return to the main menu, press the ESC key. To display the "Select Sample Circuit" screen, press ENTER. This screen contains three menus. From left to right they are the Circuits, Directories, and Drives menus. Each menu contains a sorted list of items. The LEFT and RIGHT cursor keys move from one menu to another. From within a menu you can use the UP and DOWN cursor keys to highlight an item. The PGUP and PGDN key will page through this directory. Alternatively, you can start to type out the entry to highlight the desired item. Use the ENTER key to select the highlighted item. In the Directories (middle) menu, selecting the ".." item will move you up one directory in the tree. Whenever you change the directory, the path displayed on the second line in blue will change along with the Circuits menu. In the Drives menu, you should not select a floppy drive that does not contain a diskette. Otherwise, DOS will display an "Abort, Retry, or Fail" menu. ESC will exit this menu without selecting a sample circuit. At the opening menu you can select "Exit" to exit the program without modifying the sample circuit. The program displays the "Modify Circuit" screen when a nonexistent filename is specified on the command line. This allows you to create a new circuit. By convention, logic circuit files have the extension "LG." To exit this screen, press the ESC key. You can choose to exit with or without saving the circuit. If you choose to save the circuit, it will be stored in the file (filename.LG) specified on the command line when you started the program. If a problem occurs during the writing of the file, the circuit is written to the "LOGIC.LG" file. If the DOS environmental variable TEMP or TMP is defined, the LOGIC.LG file is written to the directory identified by this variable, otherwise it is written to the default directory. If the file specified on the command line already exist, the program will display the opening menu. Your choices are: Analyze Circuit Modify Circuit Select Sample Circuit Save Circuit As Save Circuit Exit If you want to analyze a circuit and exit without modifying the file, add any character following the filename on the command line as follows: LOGIC filename.LG x Sample circuit files are in the "LG" subdirectory under the default directory. You must prefix sample filenames with "LG\" to use files in this subdirectory as follows: LOGIC LG\filename.LG x Let's look at the "NOTANDOR.LG" sample circuit. Type the following to start the program: LOGIC To exit the online tutor, press the ESC key. At the opening menu, press ENTER to select a sample circuit. Start typing "NOTANDOR" to highlight this sample circuit. Press ENTER to select it from the Circuits menu. This file actually contains three separate logic circuits. Each circuit contains a single logic gate and either a clock or two switches. The logic gates from left to right are: NOT, AND, and OR. If you press F1 twice, a help screen will identify the different types of logic gates. Notice that TRUE values are in red and FALSE values are in green. This convention is consistent with most bread board circuits that use red LEDs (Light Emitting Diodes) to identify TRUE values. Press any key to exit the help screen. When more than one adjustable component (Switch or Clock) is in a circuit: Use the LEFT and RIGHT cursor keys to select an adjustable component. Adjustable components with blue backgrounds show they have been selected. You can select an adjustable component using a mouse. Switches are Single-Pole Double-Throw. When a switch is selected: The ENTER key or the left mouse button will toggle the selected switch. The HOME and UP cursor keys will position the switch in the up or TRUE position. The END and DOWN cursor keys will position the switch in the down or FALSE position. The clock is an oscillator that automatically toggles between TRUE and FALSE. Clocks are typically used with counters. Computers use clocks to pace the Central Processing Unit (CPU) as it processes instructions. Use the "+" (plus) key to speed up the rate at which the screen is updated. Use the "-" (minus) key to slow the rate. The PGDN key will reduce the number of screen updates before the clock changes, resulting in a faster clock rate. PGUP will do the opposite slowing down the clock. When the clock is selected: The ENTER, HOME, END, UP, or DOWN cursor key stop the clock from oscillating. At this time you can manually toggle the clock with the ENTER key. This mode of operations is usefully for manually stepping a pulse through a circuit. Press the PGUP or PGDN key to return the clock to automatic oscillation. Finally, the "w" key copies the screen into a PC Paintbrush compatible file called LOGIC.PCX. If the DOS environmental variable TEMP or TMP is defined, this program writes the LOGIC.PCX file in the directory identified by this variable, otherwise it writes to the default directory. Let's look at modifying a circuit. Let's start by pressing F6 to modify the circuit. Now let's modify the first circuit on the left. Let's replace the clock with a switch. The clock is a green circle containing the letter "F" surrounded by an inverted square pulse. Use the cursor keys or the mouse to move the cursor over the clock icon. Hold the CTRL key and the BACKSPACE key down simultaneously to delete this icon. Now press F4, or the middle button on the mouse, to display the library of components. If you have a slow disk drive, it may take a few seconds to display this screen. A 256-KB disk cache, such as SMARTDRV (see your MS-DOS manual), will speed up the display of this screen. Use the cursor keys or mouse to move the white box to the icon of the switch. Press ENTER or the left mouse button to select this icon. The Modify Circuit screen will now reappear. Use the cursor keys or mouse to move the icon to the same location where the clock icon was in. Press ENTER or the left mouse button to lock it in place. If you attempt to locate the icon too close to an existing icon on the screen, you will get the message: "ERROR - Component Overlaps Another Component" Press any key to clear the message. Move the icon to another location. Press ENTER or the left mouse button to lock it in place. Icons must have some space between them. They cannot be touching. Think of each icon as having an invisible rectangular outline that encompasses the icon. If you need to move an icon: Locate the cursor on top of the icon and press the F3 key. Use the cursor keys or mouse to move the icon to a new location. Press ENTER or the left mouse button to lock it in place. We now must connect the switch to the NOT gate. Locate the cursor over the right circle (connection) of the switch, and press ENTER or the left mouse button. The icon will turn orange. Now locate the cursor over the left portion of the NOT gate and press ENTER or the left mouse button. The program will draw a connection (line) between the two connection points. You must always select a node (interconnect, fixed, switch, or clock) before selecting a logic gate (or IC) to make a connection. You can use the same procedure to remove a connection. You can connect two nodes in any order. You can press F1 for a brief help message. For additional help, press F1 a second time to receive a full screen of help. This screen identifies the different types of nodes and logic gates in the library. Press any key to exit help. Finally, press F6 to start the "Analyze Circuit" screen and see the results of your modification. Do not save the modified circuit! LOGIC There are only two logical values: "TRUE" and "FALSE." There are three fundamental logical operators from which all other logical operators. They are "NOT," "AND," and "OR." The NOT operator works as follows: If it is NOT TRUE, it must be FALSE. Conversely, if it is NOT FALSE, it must be TRUE. All of the inputs must be TRUE for the AND operator to be TRUE. Any of the inputs can be TRUE for the OR operator to be TRUE. In other words, all the inputs must be FALSE for the OR operator to be FALSE. The following table summarizes these fundamental logical operators: ╔═══════════════╦═══════════════════════════╗ ║ Input ║ Output ║ ╟───────┬───────╫────────┬─────────┬────────╢ ║ A │ B ║ NOT A │ A AND B │ A OR B ║ ╠═══════╪═══════╬════════╪═════════╪════════╣ ║ FALSE │ FALSE ║ TRUE │ FALSE │ FALSE ║ ║ FALSE │ TRUE ║ TRUE │ FALSE │ TRUE ║ ║ TRUE │ FALSE ║ FALSE │ FALSE │ TRUE ║ ║ TRUE │ TRUE ║ FALSE │ TRUE │ TRUE ║ ╚═══════╧═══════╩════════╧═════════╧════════╝ Let's take another look at the "NOTANDOR.LG" sample circuit. The triangular icon on the left is a NOT operator. This icon looks like a triangle pointing to the right followed by a circle. The circle represents the NOT operator and the triangle represents a driver. The circle will always be the opposite color (red vs. green) of the triangle showing that the logic value has changed. The AND gate is in the middle and the OR gate is on the right. Besides the fundamental logical operators, there are three additional logical operators that are commonly used and derived from the three fundamental operators. They are "NAND," "NOR," and Exclusive OR "XOR." The NAND operator is the same as "NOT AND." In other words, the NOT operator inverts the results of the AND operator. The following logical equation defines the NAND operator: A NAND B = NOT (A AND B) The "NANDNOR.LG" sample circuit depicts the NAND logic gate as an AND gate followed by a NOT gate on the left portion of the screen. Below it is the icon for the NAND logic gate that looks like the AND gate followed by a circle in the opposite color. Similarly, the NOR operator is the same as "NOT OR" and defined by the following logical equation: A NOR B = NOT (A OR B) The "NANDNOR.LG" sample circuit depicts the NOR gate as an OR gate followed by a NOT gate on the right portion of the screen. Below it is the icon for the NOR logic gate that looks like the OR gate followed by a circle in the opposite color. The Exclusive OR is similar to the OR operator, except it can only support two inputs. Only one input can be TRUE at a time for the answer to be TRUE. In other words, the answer is TRUE if one or the other input is TRUE, but not both. The logical equations for Exclusive OR (XOR) are the following: A XOR B = (A OR B) AND NOT (A AND B) or A XOR B = (A OR B) AND (A NAND B) The "XOR.LG" sample circuit depicts the logic circuit for the Exclusive OR gate, and below it is the icon for the XOR gate. Note the XOR icon is gray instead of red or green. The gray color shows this icon represents an Integrated Circuit (IC) instead of a basic logic gate. This IC contains the logic circuit displayed above. The following table summarizes the NAND, NOR, and XOR logical operators: ╔═══════════════╦═══════════════════════════════╗ ║ Input ║ Output ║ ╟───────┬───────╫───────────┬─────────┬─────────╢ ║ A │ B ║ A NAND B │ A NOR B │ A XOR B ║ ╠═══════╪═══════╬═══════════╪═════════╪═════════╣ ║ FALSE │ FALSE ║ TRUE │ TRUE │ FALSE ║ ║ FALSE │ TRUE ║ TRUE │ FALSE │ TRUE ║ ║ TRUE │ FALSE ║ TRUE │ FALSE │ TRUE ║ ║ TRUE │ TRUE ║ FALSE │ FALSE │ FALSE ║ ╚═══════╧═══════╩═══════════╧═════════╧═════════╝ DEMORGAN's THEOREM I will now discuss the DeMorgan's theorem. This theorem states: "That if you invert the input and output of the AND operator, you obtain the same results as the OR operator. Conversely, if you invert the input and output of the OR operator, you obtain the same results as the AND operator." The sample circuit "DEMORGAN.LG" depicts the equivalent AND operator using an OR operator with three NOT operators in the circuit on the left. The circuit on the right depicts the OR operator using an AND operator and three NOT operators. Also, there are several corollaries to this theorem. Listed below are the logical equations for this theorem and its corollaries: A AND B = NOT ( (NOT A) OR (NOT B) ) A AND B = (NOT A) NOR (NOT B) A OR B = NOT ( (NOT A) AND (NOT B) ) A OR B = (NOT A) NAND (NOT B) A NAND B = (NOT A) OR (NOT B) A NOR B = (NOT A) AND (NOT B) The DeMorgan's theorem can be extremely useful for reducing the total number of logic gates within a circuit when you have extra gates, but they are the wrong type. It is possible to derive the three fundamental logical operators, NOT, AND, and OR using a single logical operator, and subsequently derive all logical operators from this single logical operator. (The original computer designers only had one or two logical operator circuits to work with). This logical operator can be either an NAND or a NOR logical operator. The "NANDLOGC.LG" sample circuit uses the NAND logical operator to function as the other logical operators. The following equations also illustrate this capability: NOT A = A NAND A A AND B = NOT (A NAND B) A OR B = (NOT A) NAND (NOT B) A NOR B = NOT ( (NOT A) NAND (NOT B) ) A XOR B = NOT ( (NOT A) NAND (NOT B) NAND (A NAND B) ) A XOR B = ( A NAND (A NAND B) ) NAND ( B NAND (A NAND B) ) The NAND equivalent circuit is on top and the corresponding logic operator is below each circuit. The top left circuit represented the NOT logical operator, followed by the AND, and OR logic gates on the left side of the screen. On the top of the right side of the screen are the NOR operator and the Exclusive OR operator below it. The "NORLOGIC.LG" sample circuit uses the NOR logical operator to function as the other logical operators. The following equations also illustrate this capability: NOT A = A NOR A A AND B = (NOT A) NOR (NOT B) A OR B = NOT (A NOR B) A NAND B = NOT ( (NOT A) NAND (NOT B) ) A XOR B = (A NOR B) NOR ( (NOT A) NOR (NOT B) ) The NOR equivalent circuit is on top and the corresponding logic operator is below each circuit similar to the "NANDLOGC.LG" sample circuit. CALCULATION METHOD "Logic Gates" are circuits that do logical operations. The Logic Circuit Analysis program supports four fundamental logic gates and a 3-State logic gate. The four fundamental logic gates are AND, OR, NAND, and NOR. Each fundamental logic gate can have between one and four inputs. A one input NOR gate represents the NOT logic gate in this program. (A one input NAND gate could have represented the NOT logic gate). All the inputs for the AND gate must be TRUE for the result to be TRUE. All the inputs for the OR gate must be FALSE for the result to be FALSE. All the inputs for the NAND gate must be TRUE for the result to be FALSE. All the inputs for the NOR gate must be FALSE for the result to be TRUE. The 3-State device can have three possible results: TRUE, FALSE, and OFF. When the bottom input is FALSE, the output (right) is ON and set to the input. When the bottom input is TRUE, the output is OFF (neither TRUE nor FALSE). Computers use 3-State devices to connect multiple circuits to a bus. Only one 3-State device can be active at once. The "3STATE.LG" sample circuit illustrates the use of 3-State devices. For this example, the input is preset to TRUE for the top gate and FALSE for the bottom gate. (Instead of presetting the input, switches or logic gates could be the input.) The two 3-State devices have their outputs joined as would occur on a bus. If both devices are OFF (switches set to TRUE), the output is OFF and colored gray. Otherwise, the output color corresponds to the device that is ON. Both 3-State devices should never be ON (both switches set to TRUE) simultaneously! When an input is connected to a 3-state logic gate that is OFF, the input is treated as TRUE. This is consistent with TTL type logic gates. Inputs should never be left unconnected. The Logic Circuit Analysis program updates all the connections, then evaluates all the logic gates. Next the screen displays the results and the program waits some amount of time before starting all over. In this manner each logic gate takes the same amount of time. The "+" and "-" key adjusts the delay between screen updates speeding and slowing the screen updates. Initially, the clock will change value every eight screen updates. The PGUP and PGDN key is used to adjust the number of screen updates for the clock to change value. Electrically a clock is an oscillator. It is possible using logic gates to create a clock, as illustrated in the "CLOCK.LG" sample circuit. This circuit uses three NOT gates in series. (You may want to slow the display using the minus key). The program can support up to 1,000 logic gates, 3,000 nodes, and 7,000 connections with a maximum of eight connections per node. The 1,000 logic gates include logic gates embedded within ICs in the library and count the IC icon as well. If you press the F1 key when analyzing a circuit, the program will identify how many logic gates, nodes, and connections are in the circuit under evaluation. Press any key to resume the analysis. If you would like to learn how to build an electronic circuit to function as a logic gate, I recommend you invest in my "DC Circuit Analysis" program. This program will teach you about logic circuits made from Diodes, Diode-Transistor Logic (DTL), Transistor-Transistor Logic (TTL), Emitter-Coupler Logic (ECL), and Complementary Metal Oxide Semiconductor (CMOS) electronic circuits. ENCODERS and DECODERS Let's start by looking at encoders and decoders. A decoder takes a binary number and decodes it into one of N lines, where N is the number of different values the binary number can take on. As an example, a 2-bit binary number decodes into four lines, since there are four possible values (0, 1, 2, and 3). An encoder is the opposite of a decoder. It will take N lines and encode them into a binary number, depending on the line that is active. Since more then one input line can be active at a time, a priority is established giving preference to lines that correspond to larger binary values over lines corresponding to smaller binary values. Let's look at a 2-bit to 4-line decoder as illustrated in the "2TO4.LG" sample circuit. Notice that the two binary input lines each connect to a NOT gate creating four input lines (two normal, and two inverted). The four NAND operators form the four possible output combinations. Each NAND gate corresponds to one output line. That output is only active when it is FALSE. The logical equations for the 2-bit to 4-line decoder follow, where A is the most significant input and B is the least significant input: Output 00 (0) = NOT ( (NOT A) AND (NOT B) ) Output 01 (1) = NOT ( (NOT A) AND B ) Output 10 (2) = NOT ( A AND (NOT B) ) Output 11 (3) = NOT ( A AND B ) As you toggle the two input switches, you will observe that only one line at a time will be FALSE, the other three will be TRUE. The FALSE line is the selected line. Binary 00 (both switches set to FALSE) corresponds to the bottom line, and binary 11 (both switches set to TRUE) corresponds to the top line. Similarly, the sample circuit "3TO8.LG" illustrates the 3-bit to 8-line decoder circuit. There are one additional input bit and four additional output lines. The logical equations for the 3-bit to 8-line decoder follow, where A is the most significant input and C is the least significant input: Output 000 (0) = NOT ( (NOT A) AND (NOT B) AND (NOT C) ) Output 001 (1) = NOT ( (NOT A) AND (NOT B) AND C ) Output 010 (2) = NOT ( (NOT A) AND B AND (NOT C) ) Output 011 (3) = NOT ( (NOT A) AND B AND C ) Output 100 (4) = NOT ( A AND (NOT B) AND (NOT C) ) Output 101 (5) = NOT ( A AND (NOT B) AND C ) Output 110 (6) = NOT ( A AND B AND (NOT C) ) Output 111 (7) = NOT ( A AND B AND C ) Now that we can decode a binary number into individual lines, the next type of circuit encodes four lines into a 2-bit binary number. Other encoders are also possible. The sample circuit "4TO2.LG" illustrates a 4-line to 2-bit encoder. This circuit could be used with a four-button keypad to decide which button was pressed and encode it into a 2-bit binary value. The four switches on the left represent the keypad. The top output on the right represents the most significant bit, and the middle output represents the least significant bit. A button is pressed when a switch is set to FALSE or "0." When the lower output on the right is FALSE or "0," it shows a button has been pressed. If more than one button is pressed (set to FALSE), the encoder will respond as though the most significant (upper) switch was pressed. The following table illustrates this circuit's response, where "?" on the input shows either "0" or "1", "MSB" on the output shows the most significant output bit, "LSB" shows the least significant output bit, and "P" shows that a key was pressed. ╔═══════════════════╦══════════════════╗ ║ Input ║ Output ║ ╟────┬────┬────┬────╫──────┬─────┬─────╢ ║ B0 │ B1 │ B2 │ B3 ║ P │ MSB │ LSB ║ ╠════╪════╪════╪════╬══════╪═════╪═════╣ ║ 1 │ 1 │ 1 │ 1 ║ 1 │ 0 │ 0 ║ ║ 0 │ 1 │ 1 │ 1 ║ 0 │ 0 │ 0 ║ ║ ? │ 0 │ 1 │ 1 ║ 0 │ 0 │ 1 ║ ║ ? │ ? │ 0 │ 1 ║ 0 │ 1 │ 0 ║ ║ ? │ ? │ ? │ 0 ║ 0 │ 1 │ 1 ║ ╚════╧════╧════╧════╩══════╧═════╧═════╝ The logical equations for the 4-line to 2-bit encoder are as follows: MSB = B3 NAND B2 LSB = (NOT B3) OR (B2 AND (NOT B1)) P = B0 AND B1 AND B2 AND B3 MSB is set if either button B2 or B3 is pressed (FALSE). LSB is set if either button B3 or B1 is pressed but not B2. SELECTORS The next family of circuits I will discuss is the selectors. The selector uses a binary value to select one of N data input lines. The value of the binary input decides which data input line will be selected for output. The sample circuit "1OF2.LG" illustrates a 1 of 2-line selector with two data inputs and one selector input. The selector switch decides which of the two data inputs will be selected for output. In this example, both data inputs are set to TRUE to make it easier to track which input is reaching the output. The input on top is active when the switch is set to TRUE. The input on bottom is active when the switch is set to FALSE. The following logic equation corresponds to this sample circuit: Output = ( I0 AND (NOT S) ) OR ( I1 AND S) where: S is the selector switch, I0 and I1 are the input lines. The next sample circuit "1OF4.LG" illustrates a 1 of 4-line selector with four data inputs and a 2-bit selector. The 2-bit selector decides which of the four data inputs will be selected for output. In this example, all the data inputs are set to TRUE to make it easier to track which input is reaching the output. The top switch is the most significant binary input bit, and the bottom switch is the least significant binary input bit. The following logic equation corresponds to this sample circuit: Output = ( I0 AND (NOT S0) AND (NOT S1) ) OR ( I1 AND S0 AND (NOT S1) ) OR ( I2 AND (NOT S0) AND S1 ) OR ( I3 AND S0 AND S1 ) where: I0, I1, I2, and I3 are the data input, and S0 and S1 are the binary select input. CROSS BAR SWITCHES A telephone company can use cross bar switches to route phone calls within a telephone exchange. Each phone call is converted from an analog signal (varying voltages) to digital data (binary number representing the amplitude of the voltage). The digital data passes through the system serially (one bit at a time). Each telephone conversation is transmitted at 56 Kbps (a thousand bits per second). Consequently, only one wire per telephone is required to transmit the conversation. (A second wire is required to receive the conversation of the other party, and a third wire that is electrically connected to ground). Cross bar switches get their name from the simplest switch element that consists of two data inputs, two data outputs, and one selector input with two states. In the first state both inputs pass straight through to the output. In other words, the top input connects to the top output, and the bottom input connects to the bottom output. In the second state the two inputs cross over, such that the top input connects to the bottom output, and the bottom input connects to the top output. The simplest cross bar switch consists of two "1 of 2-line selectors" as illustrated in the "2XBAR.LG" sample circuit. In this example, the top input is preset to TRUE and the bottom input is preset to FALSE to make it easier to follow the logic. The switch represents the selector input. When the switch is set to FALSE, the two input lines pass straight through to the output. When the switch is set to TRUE, the two input lines cross over such that the top input connects to the bottom output, and the bottom input connects to the top output. A 2-input cross bar switch is not very practical by itself. However, it can be used as a building block to construct a larger cross bar switch matrix. The "4XBAR.LG" sample circuit illustrates a 4-input cross bar switch consisting of six 2-input cross bar switch elements arranged in three columns of two 2-input switch elements. Each output of the 2-input cross bar switch elements must connect to a different 2-input cross bar switch element in the next stage (column). The middle stage, the second column of switches, is required to support all the possible paths through the switch. Without a second stage, both inputs on the top cannot be transferred to the two outputs on the bottom. Every other input is preset to TRUE and the remaining inputs are preset to FALSE to make it easier to follow the logic through this circuit. Note: when all the selector switches are set to FALSE, the input passes straight through to the corresponding output. There are six selector inputs in a 4-input cross bar switch. In other words, there are 64 (2**6) possible combinations of paths the input can take to reach the output in the switch. This also means that there is more than one path a single input can take through the switch to reach the same output line. In practice, a computer controls the selector inputs and establishes which path a telephone conversation will take through the cross bar switch. When you dial another person's phone number, the computer decides which switches you will traverse and sets the selector inputs appropriately. This also means that any existing phone calls may be rerouted at this time to accommodate your phone call. On the average, a phone call takes a different path through the switch matrix every 20 seconds. More complex cross bar switches can be constructed from the 4-input cross switch element. The "16XBAR.LG" sample circuit illustrates a 16-input cross bar switch. It requires three stages (columns of switches), each consisting of four 4-input cross bar switches. There is a total of twelve 4-input switches and 72 selector inputs in a 16-input cross bar switch. Since it is impractical to connect 72 switches to the selector inputs, this sample circuit only illustrates the interconnections between each stage. Each output of the 4-input cross bar switch elements must connect to a different 4-input cross bar switch element in the next stage (column). The middle stage, second the column of switches, is required to support all the possible paths through the switch. Without a second stage, all four inputs on the top cannot be transferred to the four outputs on the bottom. Every other input is preset to TRUE and the remaining inputs are preset to FALSE to make it easier to follow the logic through this circuit. Note: this is the most complex sample circuit in this program. If you press F1 while in the Analyze Circuit screen, it will identify the total number of logic gates, nodes, and connections in this circuit. The total includes all the logic gates, nodes, and connections in each of the integrated circuit components (e.g., 4-input cross bar switch elements that in turn are constructed of 2-input cross bar switch elements). This concludes the discussion on cross bar switches. LATCHES How does computer memory work? The basis for all computer memory is the Set-Reset (S-R) Latch, which consists of two NAND gates that are cross connected. The sample circuit "SRLATCH.LG" illustrates the Set-Reset Latch. This circuit has two inputs and two outputs. The output of the top NAND gate is the normal output, and the output of the bottom NAND gate is the inverted output. The top switch Sets the latch to TRUE, when it is in the FALSE position. The bottom switch Resets the latch to FALSE, when it is in the FALSE position. When both switches are in the TRUE position, the circuit "remembers" its last setting. However, both switches should not be in the FALSE position, since both outputs (which are supposed to be opposites of each other) will both become TRUE. The next sample circuit we will look at is "SRLATCHE.LG," which contains a Set-Reset Latch with Enable. This circuit consists of four NAND gates, where the two on the right are the same Set-Reset latches discussed above, and the two NAND gates on the left are used to implement the Enable function. The switch in the middle is the Enable input that must be TRUE before either the Set or Reset switch will take effect. When the Enable switch is FALSE, the circuit remembers its last setting. Initially, this circuit will oscillate. The oscillation is due to the unknown initial state at power up. (Most real circuits have a power on reset to prevent oscillation). You must set the Enable switch to TRUE, and either the Set or Reset switch TRUE to stop the oscillation and establish a known state. The switch on the top is the Set input, and works opposite of the Set discussed in the previous circuit. When Set is TRUE, the Latch will be set to TRUE. Similarly, when the Reset switch is TRUE, the latch will be set to FALSE. When both Set and Reset switches are set to FALSE, the circuit remembers the last setting. The Data Latch is an improvement on the Set-Reset Latch. The "DLATCH.LG" sample circuit illustrates the Data Latch. This circuit consists of four NAND gates, where the two NAND gates on the right form the familiar Set-Reset Latch described above. The top switch is the Data input, and the bottom switch is the Enable input. When the Enable switch is TRUE, the Data input is stored in the latch. When the Enable switch is FALSE, the Data input is ignored, and the circuit remembers its last setting. Initially, this circuit will oscillate. You must set the Enable switch TRUE to stop the oscillation. FLIP-FLOPS The next type of logic circuit I will discuss is the Master-Slave Flip-Flop. A Flip-Flop consists of two latches connected in series. Flip-Flops are used to create registers, shift registers, and counters which are discussed in a later section. The Set-Reset Flip-Flop is an example of a Master-Slave Flip-Flop. It consists of two latches connected in series and illustrated in the "SRFF.LG" sample circuit. Both latches are Set-Reset Latches with Enable as described above. When the Enable input is TRUE, the value of the first (Master) latch is Set or Reset as described above. When the Enable input is FALSE, the value stored in the first latch transfers to the second (Slave) latch. Initially, this circuit will oscillate. You must set either the Set or Reset switch to TRUE and toggle the Enable switch to TRUE and back to FALSE to stop the oscillation. The sample circuit "SRFFSC.LG" depicts a Set-Reset Flip-Flop with Preset and Clear inputs. This Flip-Flop is similar to the previously discussed Set-Reset Flip-Flop, except it has additional inputs called "Preset" and "Clear." The Preset input is the switch on top and the Clear input is the switch on the bottom. These additional inputs eliminate the initial oscillation and allow this Flip-Flop to initialize to either a TRUE or a FALSE value. When the Set input is FALSE, both latches in the Flip-Flop are set TRUE. When the Clear input is FALSE, both latches are set to FALSE. If both Preset and Clear are FALSE, both outputs are set TRUE, similar to when the original Set-Reset Latch had both Set and Reset inputs set to FALSE. The Data Flip-Flop is another example of a Master-Slave Flip-Flop. It consists of two latches connected in series as illustrated in the "DFF.LG" sample circuit. The first (Master) latch is a Data Latch and the second (Slave) latch is a Set-Reset Latch with Enable. When the Enable input is TRUE, the value of the Data input transfers to the first latch. When the Enable input is FALSE, the value stored in the first latch transfers to the second latch. Initially, this circuit will also oscillate. You must toggle the Enable switch to TRUE and back to FALSE to stop the oscillation. The sample circuit "DFFSC.LG" depicts a Data Flip-Flop with Preset and Clear inputs. This Flip-Flop is similar to the previously discussed Data Flip-Flop, except it has additional inputs called "Preset" and "Clear." The Preset input is the switch on top and the Clear input is the switch on the bottom. These additional inputs eliminate the initial oscillation and allow this Flip-Flop to initialize to either a TRUE or a FALSE value. When the Preset input is FALSE, both latches in the Flip-Flop are set TRUE. When the Clear input is FALSE, both latches are set to FALSE. If both Preset and Clear are FALSE, both outputs are set TRUE, similar to when the original Set-Reset Latch had both Set and Reset inputs set to FALSE. The "J-K" Flip-Flop or the Toggle Flip-Flop is the last type of Flip-Flop I will discuss. The J-K Flip-Flop is identical to the Set-Reset Flip-Flop with Preset and Clear, except the output of the Slave latch is cross connected to the input of the Master latch, forcing it to toggle when a clock is connected to the Enable input. The sample circuit "JKFFSC.LG" illustrates the J-K Flip- Flop with Preset and Clear. The "J" input corresponds to the "Set" input and the "K" input corresponds to the "Reset" input. For this Flip-Flop to toggle, all the inputs (J, K, Preset, and Clear) must be TRUE. When the Preset input is FALSE, both latches in the Flip-Flop are set TRUE. When the Clear input is FALSE, both latches are set to FALSE. If both Preset and Clear are FALSE, outputs on both latches are set TRUE, similar to when the original Set-Reset Latch had both Set and Reset inputs set to FALSE. REGISTERS Registers, shift registers and counters are constructed from Flip-Flops. The simplest use of Flip-Flops is a register. A register is memory used within a Central Processing Unit (CPU) to temporarily hold information. A 4-bit register consists of four Data Flip-Flops as illustrated in the sample circuit "REGISTER.LG." In this example, the input data is preset to TRUE, FALSE, TRUE, and FALSE. The Clear switch is on the bottom. When the Clear switch is FALSE, all the Flip-Flops reset to FALSE. The other switch on the left is the Enable switch. When the Enable switch is TRUE, input data transfers to the output of the Flip-Flop. The next use of Flip-Flops we will explore is the Shift Register. Shift Registers can take serial input data (one bit at a time) and output parallel data. They can also take parallel input data (four or more bits at once) and output serial data. An example of serial data is using the COM1: port to communicate with another computer via a modem. An example of parallel data is using the LPT1: port to communicate with a printer. The Shift register consists of multiple Data Flip-Flops connected in series, requiring one Flip-Flop for each bit in parallel. The Serial input enters the left Flip-Flop and the Serial output exits the right Flip-Flop. The parallel output is simply reading the output of each Flip-Flop simultaneously. The first shift register we will look at converts Serial input to Parallel Output. The sample circuit "SPSHREG.LG" illustrates a Shift Register. The top switch represents the serial input and the bottom switch is the Clear input. When the Clear switch is FALSE, the shift register resets. When it is TRUE, data will shift through the Flip-Flops from left to right with each clock pulse. Note that the Preset ("s") input on each Flip-Flop is not used. By default it is assumed to be TRUE. The parallel output is always available by reading the output (Q) of each Flip-Flop. The next circuit we will look at is a parallel to serial Shift Register as illustrated in the "SHIFTREG.LG." It also uses Data Flip-Flops, but has the added ability to load data in parallel. In reality, this arrangement can be used to convert serial to parallel as well as parallel to serial. A pair of AND gates and one OR gate are used to decide if data should be loaded or the value of the previous Flip-Flop should be loaded in to the next Flip-Flop in series. The switch at the very top loads data when it is FALSE, or count when it is TRUE. The switch at the bottom is the Clear input and it must be TRUE to count, or FALSE to reset all the Flip-Flops. The switch in the middle represents the serial input data. In this example the parallel input data is fixed using the following values (TRUE, FALSE, TRUE, FALSE). BINARY NUMBERS Before we can discuss counters, we must discuss binary numbers. A digital computer is a "Binary" computer. Binary computers deal with only two states: TRUE or FALSE, 1 or 0, On or Off, Voltage or Ground. Binary computers do not use varying voltages to represent values, instead they use simple On/Off circuits. The binary value 1 corresponds to TRUE, and the binary value 0 corresponds to FALSE. The decimal numbering system, which we are familiar with, uses ten different digits (0 through 9), and is called base 10. A binary computer represents numbers using base 2, which only has two digits "0" and "1." In base 10, the least significant (right most) digit is multiplied by 1 (10**0), the next digit by 10 (10**1), 100 (10**2), 1000 (10**3), etc. In base 2, the least significant digit is multiplied by 1 (2**0), the next by 2 (2**1), 4 (2**2), 8 (2**3), etc. So the decimal number 9 can be represented by the binary number 1001. The following table depicts the first sixteen (starting with zero) binary and decimal numbers: ╔════════╤═════════╗ ║ Binary │ Decimal ║ ╟────────┼─────────╢ ║ 0000 │ 0 ║ ║ 0001 │ 1 ║ ║ 0010 │ 2 ║ ║ 0011 │ 3 ║ ║ 0100 │ 4 ║ ║ 0101 │ 5 ║ ║ 0110 │ 6 ║ ║ 0111 │ 7 ║ ║ 1000 │ 8 ║ ║ 1001 │ 9 ║ ║ 1010 │ 10 ║ ║ 1011 │ 11 ║ ║ 1100 │ 12 ║ ║ 1101 │ 13 ║ ║ 1110 │ 14 ║ ║ 1111 │ 15 ║ ╚════════╧═════════╝ A binary digit is called a "bit." So far we only discussed 4-bit (four binary digits) binary numbers. Computers can handle larger numbers, such as 8-bit (0 through 255), 16-bit (0 through 65,535), and 32-bit (0 through 4,294,967,295). The largest value is calculated by raising 2 to the power of N and subtracting one from this value, where N is the number of binary digits (bits) used to represent the number. We will concentrate on the 4-bit numbers. COUNTERS The next subject I will discuss is Counters. They use J-K Flip-Flops that toggle in response to a clock pulse. The output of each Flip-Flop is half the frequency of the input clock rate. By connecting the J-K Flip-Flops in series, we can form counters, one Flip-Flop for each bit in the counter. The least significant bit is on the left and the most significant bit is on the right, which is opposite of the way binary numbers are written. The first counter we will look at is a 4-bit Asynchronous counter. It is Asynchronous because the change of each Flip-Flops ripples through the counter from left to right, instead of occurring simultaneously. The sample circuit "COUNTER.LG" illustrates this counter. When the switch is in the FALSE position, the counter is cleared and not counting. When the switch is TRUE, the counter will count from 0 to 1111 (15). There are four output bits, corresponding to the normal output labeled "Q" in the upper right-hand corner of each Flip-Flop. You may find it easier to put the clock in manual mode and use the ENTER key to step though counting sequence. Use the PGUP or PGDN key to return the clock to automatic mode. Notice: the J, K, and Set inputs are not connected to anything. They are treated as TRUE by this program. In a real circuit, you should explicitly connect them to a TRUE source, and not leave them unconnected. The next counter we will look at is a 4-bit Synchronous counter. It is Synchronous because the change of each Flip-Flop occurs simultaneously. The sample circuit "SYNCOUNT.LG" illustrates this counter. It also has a switch that clears the counter when set to FALSE and allows it to count when set to TRUE. The AND gates synchronize all the Flip-Flops. Both the J and K input connect to the output of an AND gate. The input of the AND gate connects to all the previous Flip-Flop outputs. The net effect is that the Flip-Flops will only toggle when all the previous Flip-Flops are TRUE. The next counter type is a 4-bit Synchronous counter with the ability to load data. The "LSCOUNT.LG" sample circuit illustrates this circuit. This counter is similar to the previous example, except logic has been added to allow the counter to be preset to input data. The AND gates on top synchronize the Flip-Flops. The input data is represented by the fixed nodes (TRUE, FALSE, TRUE, FALSE) connected to the OR gates on the bottom. All switches must be TRUE to count. A FALSE value on a switch presets, clears, or loads data. The switch just above the clock enables or disables the clock. The switch just below the clock sets (loads) the counter the input data. The switch at the bottom clears the counter. The switch at the top presets the counter to all TRUE values. The last counter type is an Up-Down Synchronous counter as illustrated in the "UDCOUNT.LG" sample circuit. The top switch decides if the counter will count forward (up) or reverse (down). A TRUE value selects forward counting, and a FALSE value selects reverse counting. The bottom switch decides if the counter will be cleared (all output set to FALSE) or count. A TRUE value means count, and a FALSE value means clear. BINARY ARITHMETIC How does a digital computer perform arithmetic calculations? The Exclusive OR logical operator is the fundamental basis for a binary adder. Once you can add two numbers together, you can than subtract two numbers by converting one number to its negative value and adding it to the other number. Let's start with the "Half-Adder." This circuit adds two binary digits together and has two outputs: Sum and Carry. The Half-Adder is a variation on the Exclusive OR circuit. The "HALFADD.LG" sample circuit illustrates the Half-Adder, as described by the following logical equations: Sum = A XOR B Carry = A AND B The two switches on the left represent the input. The AND gate represents the Sum output. The NOT gate represents the Carry output. The truth table for a Half-Adder follows: ╔═══════╦════════════╗ ║ Input ║ Output ║ ╟───┬───╫─────┬──────╢ ║ A │ B ║ Sum │ Carry║ ╠═══╪═══╬═════╪══════╣ ║ 0 │ 0 ║ 0 │ 0 ║ ║ 0 │ 1 ║ 1 │ 0 ║ ║ 1 │ 0 ║ 1 │ 0 ║ ║ 1 │ 1 ║ 0 │ 1 ║ ╚═══╧═══╩═════╧══════╝ The "Full-Adder" is essentially two Half-Adders in series. The Full-Adder has three inputs: A, B, and Carry (C) from the previous least significant digit. It also has two outputs: Sum and Carry. The "FULLADD.LG" sample circuit illustrates a Full-Adder, as described by the following logical equations: Sum = (A XOR B) XOR C Carry = (A AND B) OR (A AND C) OR (B AND C) The two switches on the left represent the input to the adder. The third switch in the middle represents the carry input from another Full-Adder. (Mathematically it does not matter which switch represents the data input or the carry input. However, by connecting the carry input to the middle switch, the number of gates the carry must pass through is kept to a minimum.) The AND output represents the Sum output and the NAND output represents the Carry output. The truth table for a Full-Adder follows: ╔═══════════╦════════════╗ ║ Input ║ Output ║ ╟───┬───┬───╫─────┬──────╢ ║ A │ B │ C ║ Sum │ Carry║ ╠═══╪═══╪═══╬═════╪══════╣ ║ 0 │ 0 │ 0 ║ 0 │ 0 ║ ║ 0 │ 0 │ 1 ║ 1 │ 0 ║ ║ 0 │ 1 │ 0 ║ 1 │ 0 ║ ║ 0 │ 1 │ 1 ║ 0 │ 1 ║ ║ 1 │ 0 │ 0 ║ 1 │ 0 ║ ║ 1 │ 0 │ 1 ║ 0 │ 1 ║ ║ 1 │ 1 │ 0 ║ 0 │ 1 ║ ║ 1 │ 1 │ 1 ║ 1 │ 1 ║ ╚═══╧═══╧═══╩═════╧══════╝ Full-Adders can be connected in series to handle larger numbers. A 4-bit Adder uses four Full-Adders connected in series, where the Carry output of the least significant Full-Adder becomes the Carry input of the next significant Full-Adder. The sample circuit "4BITADD.LG" illustrates this circuit. The upper row of switches represents the first 4-bit number, and the lower set of switches represents the second 4-bit number. Note that the least significant bit is on the left and the most significant bit is on the right, which is the reverse order that binary numbers are usually written. The carry input of the least significant adder is preset to zero (FALSE). Larger number can be added using more Full-Adders in series. Today's computers support 16-bit and 32-bit arithmetic. The carry output must ripple from left to right through the adder. If you had a 16-bit or a 32-bit adder, the time for the carry to ripple through all the Full-Adders is excessive. Production adders us a "Fast Carry" circuit to calculate all the carries simultaneously. Unfortunately, the number of additional logic gates makes the screen too cluttered to follow what is happening. The 4-bit Adder in the library employees the "Fast Carry" logic. Negative numbers are represented by using a method called "Two's-Compliment." This method has the property that when a positive number is added to its negative counter part number, the answer is zero with the carry output set to one. As an example, a negative one is the largest possible number (all binary ones). The following table displays all sixteen possible binary numbers in a 4-bit word and the corresponding decimal numbers when using Two's-Compliment: ╔════════╤═════════╗ ║ Binary │ Decimal ║ ╟────────┼─────────╢ ║ 0000 │ 0 ║ ║ 0001 │ 1 ║ ║ 0010 │ 2 ║ ║ 0011 │ 3 ║ ║ 0100 │ 4 ║ ║ 0101 │ 5 ║ ║ 0110 │ 6 ║ ║ 0111 │ 7 ║ ║ 1000 │ -8 ║ ║ 1001 │ -7 ║ ║ 1010 │ -6 ║ ║ 1011 │ -5 ║ ║ 1100 │ -4 ║ ║ 1101 │ -3 ║ ║ 1110 │ -2 ║ ║ 1111 │ -1 ║ ╚════════╧═════════╝ To subtract two numbers, a computer uses the adder circuit and adds one number to the negative of the other number. To obtain the negative of the other number, we invert each bit using the NOT gate and add one. The negative of a number is calculated using the "Two's-Compliment" method as follows: -A = (NOT A) + 1 The subtraction circuit uses the adder circuit, where the NOT gate is used to invert the second number and the carry input is set to TRUE, to effectively add one to the answer. Finally, it inverts the carry out with a NOT gate so the only time Carry out is TRUE, is when the answer is negative. The "4BITSUB.LG" sample circuit illustrates the 4-bit subtraction circuit. This circuit solves the equation: C = A - B The top row of switches is the A value, and the bottom row of switches is the B value. The answer is the sum output of each adder. In all cases, the least significant bit is on the left and the most significant bit is on the right. This brings us to the next topic, multiplication. To multiply two numbers together, we will also use the adder circuit. If we remember how long hand multiplication is performed using decimal numbers, the same method applies to binary numbers. Let's look at the decimal multiplication of 12 times 14: 14 x12 ─── 28 +14 ──── 168 The same two numbers can be multiplied together using binary numbers as follows: Binary Decimal 1110 14 x1100 x12 ───── ─── 0000 0 0000 0 1110 56 +1110 +112 ──────── ──── 10101000 168 If we look at this method, we will observe that it is nothing but a series of shifts and adds. Start with zero as the answer. Look at the least significant bit of the multiplier, if it is one, add the other number to the answer, otherwise skip this addition if it is zero. Next shift the other number one place to the left and look at the next significant bit in the multiplier. Repeat this process for each bit in the multiplier. Notice that 4-bit multiplication can result in an 8-bit answer. The "MULTIPLY.LG" sample circuit illustrates a 4-bit multiply circuit. This circuit contains four adder circuits. The bottom left adder adds the first two results, and the bottom right adder adds the last two results. The top adders add the results of the adders on the bottom. In this method there are no clock cycles or shift steps required. The four switches on the left represent one value, and the four switches on the bottom represent the other value. Note that all numbers are represented with least significant bit on the left, instead of most significant bit as depicted when written on paper. The 10-bit answer is displayed across the top of the screen. This circuit only handles positive numbers. To multiply a mix of positive and negative numbers, requires additional circuits to convert negative numbers to positive before performing the multiplication, and when necessary converting the answer to a negative number after performing the multiplication. A computer can perform division, by using a series of shifts and subtractions. To start, the divisor is shifted all the way to the left. Next subtract the divisor from the numerator. If the resulting subtraction is positive, the next bit of the answer is set to one and the numerator is replaced with the results of the subtraction. If the resulting subtraction is negative, (the divisor is larger then the numerator), the numerator does not change and the next bit in the answer is zero. Finally, the divisor and the answer are shifted right one place and the process continues. When dividing two 4-bit numbers, the answer consists of a 4-bit quotient and a 4-bit remainder. As an example, if we divide 11 by 2, the quotient is 5 and the remainder is 1. Let's look at this same example using binary numbers: Binary Answer Decimal 1011 11 -0010000 -16 (2*8) ──────── ─── (negative) 0 (negative) 1011 11 -0001000 - 8 (2*4) ──────── ─── 0011 1 3 0011 3 -0000100 - 4 (2*2) ──────── ─── (negative) 0 (negative) 0011 3 -0000010 - 2 (2*1) ──────── ─── 0001 1 1 The answer is 0101 (5) with a remainder 0001 (1). When the subtraction results in a positive number, the answer is one, otherwise zero. The remaining value after all four subtractions is the remainder. The 4-bit divide circuit is too complicated to be shown on the screen, but can be found in the Library of Components. Today's computers typically use 16 or 32 bits to represent integers. Therefore, they can represent larger numbers. 16-bit integers can be as large as 32,767 and 32-bit integers can be as large as 2,147,483,647. FLOATING POINT ARITHMETIC So far we have explored arithmetic of whole numbers called integers. Integers can be positive or negative, but only whole numbers (e.g., 0, 1, 2). This brings us to the next topic called floating point numbers. Floating point numbers contains a decimal point (e.g., 3.1416). Floating point numbers get their name from fact that the decimal point can be moved within a number maintaining the same number of digits (precision) but take on different values. As an example, numbers with six decimal places of precision include: 12345.6 and 1.23456. Floating point numbers are usually represented in scientific notation. Scientific notation for base 10 numbers is a number times ten raised to a power. As an example 12345.6 can be represented as: 1.23456 x 10**4 where "**" means raised to the power, so 10**4 is 10x10x10x10 or 10,000 The number is usually shown with one digit to the left of the decimal point. In general, floating point numbers are less accurate than integers, since fractional numbers are represented by a finite precision, and some numbers require infinite precision to be properly represented. As an example the fraction 1/3 corresponds to 0.33333333 ..., where an infinite number of threes are required to accurately represent this fraction. Scientific notation supports positive and negative numbers. It also supports positive and negative exponents. The following are several examples: +1.23456 x 10**4 -1.23456 x 10**4 +1.23456 x 10**(-4) -1.23456 x 10**(-4) The computer uses base 2 to represent floating point numbers. A floating point number consists of three components: sign, exponent, and mantissa. The sign determines if the number is positive or negative. The exponent determines the power that two is raised to, and the mantissa represents the normalized number. As an example: the decimal number 5 can be represented as the following binary number in scientific notation. +1.01 x 2**10 Where the "+" sign at the front of the number specifies the sign, showing the number is positive. 1.01 is the mantissa and the binary value 10 (decimal 2) is the exponent. The exponent shows that the decimal point should be moved two places to the right. Therefore +1.01 x 2**10 becomes: 101.0, which corresponds to a decimal 5. The fraction 3/8 can be represented by the following floating point number: +1.1 x 2**(-10) Since the exponent is negative, the decimal point must be moved to the left two binary place resulting in the value 0.011 that corresponds to 3/8. There are many possible ways to represent a floating point number in a computer. Let's look at a hypothetical 8-bit format that I designed for use with this program. This format consists of a 1-bit sign, 3-bit exponent, and 4-bit mantissa as follows: s eee mmmm where: s is the sign bit, 0 = positive, 1 = negative eee is the exponent, where 011 corresponds to 2**0 mmmm is the mantissa, which is left justified By convention when the sign bit is zero, the number is positive. Conversely, when the sign bit is one, the number is negative. Now comes the tricky part. How do we represent negative exponents? We could use two's-compliment. I instead choose a format that is more consistent with how computers actually store this value. By convention an exponent value of 011 corresponds to an exponent of zero. Values greater than 011 are positive exponents and values less then 011 are negative exponents. The mantissa is very straight forward. It is always left justified such that the left most bit is always a one. As an example the previously discussed numbers are transformed into the following 8-bit floating point format: Floating-Point Binary Binary Notation Scientific Decimal s eee mmmm Notation Notation - --- ---- --------------- -------- 5 = 0 101 1010 or 1.01 x 2**10 or 101.0 -5 = 1 101 1010 or -1.01 x 2**10 or -101.0 3/8 = 0 001 1100 or 1.10 x 2**(-10) or 0.011 -3/8 = 1 001 1100 or -1.10 x 2**(-10) or -0.011 Obviously, no computer would attempt to use an 8-bit floating point format. But this format will be useful in showing how floating point numbers are manipulated. The Institute of Electrical and Electronic Engineers (IEEE) 754 specification defines the most widely used floating point formats in today's computers. They are the IEEE 32-bit and IEEE 64-bit floating point formats. The Intel math coprocessor uses these two formats and an additional 80-bit floating point format. The following table summarizes these floating point formats: ╔════════╤═══════╤══════════╤══════════╗ ║ Format │ Sign │ Exponent │ Mantissa ║ ╟────────┼───────┼──────────┼──────────╢ ║ 32-bit │ 1-bit │ 8-bit │ 23-bit ║ ║ 64-bit │ 1-bit │ 11-bit │ 52-bit ║ ║ 80-bit │ 1-bit │ 15-bit │ 64-bit ║ ╚════════╧═══════╧══════════╧══════════╝ The sign bit is always first, followed by the exponent, and finally the mantissa. The sign bit is zero for positive numbers and one for negative numbers. The exponents are stored as a positive number. To represent negative exponents values, the exponent is biased by half it possible value. For 8-bit exponents the bias is 127, for 11-bit exponents the bias is 1,023, and for 15-bit exponents the bias is 16,383. You compute the actual exponent value by subtracting the bias value from the exponent value. As an example, an exponent of -5 in an 8-bit exponent would be represented by 127 - 5 = 122 (base ten) or 0111111 - 00000101 = 01111010 (base 2). The IEEE formats have one twist concerning the handling of the mantissa. The mantissa is stored as a binary fraction greater than or equal to one and less than two. The mantissa is always left justified and the first bit is always a one (well almost always). The first bit is not actually stored in the format, instead it is assumed to be one and the next 23 or 52 bits are the remainder of the number. In this manner an additional bit of precision is obtained for the 32-bit and 64-bit formats. In other words, the 32-bit format has 24 bits of precision and the 64-bit format has 53-bits of precision. The only exception is the number zero, which is always represented by all zeros (sign, exponent, and mantissa). This is a special case, since the exponent is never allowed to be all zeros for a non-zero number. How big of a number can these floating point formats represent? This is not a simple question. Let's analyze the IEEE 32-bit format. The 23-bit mantissa can represent numbers as large as 2**24 (since the first bit is always assumed to be one). 2**24 is approximately 1.7 x 10**7. In other words the mantissa is equivalent to a seven decimal place number. The 8-bit exponent is in effect ±2**7 or ±128. Remember this is the value of the exponent, we must still raise two to this power. Hence the largest number is 2**128 or approximately 3.4 x 10**38. So the proper answer to the question "How big of a number can the IEEE 32-bit format handle?", is a seven decimal place number within the range ±3.4 x 10**38. There is actually another limit we have not discussed, and that is how small of a number can be represented as the number approaches zero? The answer is 2**(-126) or approximately 1.2 x 10**(-38). With the limitation on how large and how small a number can handle, there are some error conditions that must be addressed. The first is called an "Over-Flow" condition. Which means the resulting number is too large to be represented by the floating point format. Think of multiplying two very large 32-bit floating point numbers together and the result being larger than 3.4 x 10**38. This error shows that the exponent could not represent the resulting number and therefore the exponent over flowed. The next error condition is called an "Under-Flow" condition. This occurs when a number becomes two small as it approaches zero. As an example if we divide a very small number by a very large number, the result can be smaller than 1.2 x 10**(-38). In this case the exponent becomes two small to represent the number and therefore it under flowed. The last error condition I will mention is the division by zero. Other error conditions also exist and are defined by the IEEE 754 specification. The following table summarizes the three floating point formats in terms of their decimal limits: ╔════════╤═══════════╤═══════════════╤══════════════════╗ ║ Format │ Precision │ Largest Value │ Smallest Value ║ ╟────────┼───────────┼───────────────┼──────────────────╢ ║ 32-bit │ 7 places │ ±3.4x10**38 │ ±1.2x10**(-38) ║ ║ 64-bit │ 15 places │ ±1.8x10**308 │ ±2.2x10**(-308) ║ ║ 80-bit │ 19 places │ ±1.2x10**4932 │ ±3.4x10**(-4932) ║ ╚════════╧═══════════╧═══════════════╧══════════════════╝ Let's discuss 32-bit floating point arithmetic, starting with addition. We cannot simply add the two mantissas together using an integer addition circuit. We must first decide which number is larger, i.e., which exponent is larger. The smaller exponent is subtracted from the larger exponent. The resulting number is the number of binary places the smaller number's mantissa must be shifted to the right before being added to the larger number. Since the mantissa is always positive, the sign bit determines if we add or subtract these numbers. The following example looks at adding 5 and -3/8: 5 0 10000001 01000000000000000000000 -3/8 1 01111101 10000000000000000000000 Step 1: Determine the Larger Exponent. The exponent for 5 is larger than the exponent for -3/8 Step 2: Subtract the smaller exponent from the larger exponent: 10000001 (+2) -01111101 (-2) ───────── 00000100 (+4) Step 3: Restore the leading 1 to each mantissa 101000000000000000000000 110000000000000000000000 Step 4: Shift the smaller number to the right the calculated number of places (4 places) 101000000000000000000000 0000110000000000000000000000 Step 5: Check sign bit and decide if we add or subtract these numbers. There are four possibilities that have to be addressed. ╔═══════╦═════════╤════════╗ ║ Input ║ │ ║ ╟───┬───║ Action │ Result ║ ║ A │ B ║ │ ║ ╠═══╪═══╬═════════╪════════╣ ║ + │ + ║ A + B │ + ║ ║ + │ - ║ A - B │ ? ║ ║ - │ + ║ B - A │ ? ║ ║ - │ - ║ A + B │ - ║ ╚═══╧═══╩═════════╧════════╝ In this case we subtract the smaller number from the larger number using a 24-bit addition (or subtraction) circuit. 101000000000000000000000 -000011000000000000000000 ───────────────────────── 100101000000000000000000Step 6: If necessary, shift the mantissa such that a one is always in the first column. If we added two numbers together, it is possible that a carry condition would occur and the number would have to be shifted to the right one place. If we subtracted two numbers of comparable size, it is possible the answer may have to be shifted as much as 23 places to the left. Note that floating point subtraction can result in significant loss in precision. For each place to the right we shift the number we must increment the exponent of the larger number. For each place to the left we shift the number we must decrement the exponent by that many places. In this example it was not necessary to shift the answer or adjust the exponent. Step 7: The next step is to determine the sign of the answer. Again refer to the four possibilities identified in step 5. In this example, the sign bit should be positive, since the result is a positive number. Step 8: Store the answer in a floating point format. 0 10000001 001010000000000000000000 (4 5/8) If the smaller number's exponent is less than the larger number's exponent by more than the number of precision bits in the mantissa, it will not contribute at all to the answer. As an example if the exponent of a 32-bit floating point number is 56 for the larger number and 26 for the smaller number, the difference is 30. Since there are only 24 bits in the mantissa, we would have to shift the smaller number 30 places to the right before adding it to the larger number. It would not contribute to the answer. For floating point subtraction, we simply use the floating point addition, as described above, except we invert the sign of the second number using a NOT gate. In other words, if the second number is positive we make it negative, or vice versa. Fortunately, the floating point multiply is much simpler. Let's first look at a simple decimal example. If we multiply 1 x 10**4 times 2 x 10**5, the answer is 2 x 10**9. This multiply can be viewed as 1 times 2 and 10**4 times 10**5. 1 times 2 is obviously 2. To multiply 10**4 by 10**5 we can simply add the exponents (4+5) and get 10**9. Similarly, in a floating point format all we do is add the exponents and multiply the mantissas. In the following example we will multiply 5 by -3/8: Step 1: Restore the leading 1 to each mantissa 101000000000000000000000 110000000000000000000000 Step 2: Multiply the two mantissas together. Note the answer requires twice as many bits as the numbers being multiplied. In this example, two 24-bit numbers result in a 48-bit answer. However, since we will only store 24-bits of the answer, we only need to multiply the first 13-bits of each mantissa using a 13-bit integer multiply circuit. 1010000000000 x1100000000000 ─────────────────────────── 101000000000 +101000000000 ─────────────────────────── 011110000000000000000000000 In this example the resulting left most bit is a zero and should be discarded. Sometimes the resulting left most bit will be a one. In those cases, you do not discard the first digit, and must increment the results of the exponent calculation. Step 3: Next we add the two exponents using an 8-bit adder. To correct for the bias of 01111111, which could be subtracted from each exponent be fore added, and added back afterward, or we could add the two exponents unchanged and then subtract the bias once. 10000001 +01111101 ───────── 11111110 -01111111 ───────── 01111111 The new exponent becomes 01111111. Step 4: Calculate the sign bit. Since we are multiplying two number together, the resulting sign bit is the Exclusive OR of the two bits. Sign bit = A XOR B 1 = 1 XOR 0 Therefore, if one and only one of the numbers is negative, the answer is also negative. Step 5: Store the answer in a floating point format. 1 01111111 111000000000000000000000 (-1 7/8) Let's look at the "FPMULTP.LG" sample circuit. In this circuit we are using my hypothetical 8-bit floating point format described earlier. It consisted of a 1-bit sign, followed by a 3-bit exponent, and a 4-bit mantissa. Unlike the IEEE format, we will preserve the leading 1 in the mantissa. The top row of switches represents the first number and the bottom row of switches represents the second number. The switches are organized into three groups: The left group of switches represents the sign bit, the middle group of switches represents the exponent, and the right group of switches represents the mantissa. The exponent and mantissa are organized in the order you would write the number on paper with the most significant bit on the left and the least significant bit on the right. The answer is the output nodes along the top of the screen. Since the Add and Multiply library circuits are organized in reverse order (least significant bit on left and most significant bit on right) the connections cross over on both input and output. Finally, the "A or B" library item in the upper right-hand portion of the screen is a 4-bit wide 1 of 2 selector used to correct the condition when the resulting most significant bit is zero by shifting the answer one bit to the left or subtracting one from the exponent. (The sample circuit "AORB.LG" illustrates the 4-bit wide 1 of 2 selector). Let's plug in some real values to see how it works. In this example we will multiply 5 times -3/8. You should set the switches as follows where 0 corresponds to FALSE and 1 corresponds to TRUE: s eee mmmm - --- ---- 5: 0 101 1010 -3/8: 1 001 1100 The answer should be -1.875 (-1 7/8) or 1 011 1111 in binary. You are welcome to try other combinations of numbers. Floating point division is very similar to floating point multiplication. Except the exponents are subtracted and the bias is added back in. The mantissas are divided instead of multiplied. Unlike, integer division where we have a quotient and a remainder, there is no concept of a remainder in floating point division. The circuit must continue to shift and subtract until the answer has the required significant bits. If the two mantissas are nearly the same value, the division circuit may have to shift as much as twice the number of bits in the mantissa before obtaining the answer. ARITHMETIC LOGIC UNIT (ALU) Now that we looked at logic circuits and arithmetic circuits, it is time to look at how a computer would use these circuits. A computer only understands "machine language" which consists of binary numbers. To program a computer in machine language you normally use a language called "Assembly Language" where each line corresponds to a single machine language instruction. We will only discuss the following hypothetical 8 assembly language instructions: Assembly Logical Language Equations Description -------- ----------- ------------- NOT A A = NOT A (Inverter) AND A, B A = A AND B (Logical And) OR A, B A = A OR B (Logical Or) XOR A, B A = A XOR B (Exclusive Or) INC A A = A + 1 (Increment) DEC A A = A - 1 (Decrement) ADD A, B A = A + B (Addition) SUB A, B A = A - B (Subtraction) Notice the answer is always stored in A. For this reason A is usually called the accumulator. We will only discuss integer arithmetic. Let's start by looking at how a computer implements logic circuits. The computer applies the logical operators (NOT, AND, OR, or XOR) to each bit separately. The number of logic gates required to implement these instructions depends on the number of bits in a particular computer's word. In our example, we will be using 4-bits per word. A typical computer would use 16-bits or 32-bits per word. (Some computers may use less, like 8-bits per word, and some computers may use more, like 64-bits per word). In other words, a 4-bits per word requires four logic gates, one for each bit. The least significant bit of word A will be paired with the least significant bit of word B. The remaining three bits in word A would be paired with their corresponding bits in word B. The "LU.LG" sample circuit illustrates the computer "Logic Unit." This circuit implements the 4-bit NOT, AND, OR, and XOR instructions. Word A is represented by the fixed values TRUE, FALSE, TRUE, FALSE. Word B is represented by the fixed values TRUE, TRUE, FALSE, FALSE. There are three inputs to this circuit, all of which enter the "2 to 4" circuit. The right most switch, connected to the left input of the "2 to 4" circuit, enables this circuit when it is set to FALSE. When it is set to TRUE, this circuit disables all the 3-state units. When this switch is set to FALSE, the circuit is enabled, and the remaining two switches are used to select the appropriate logical operator (NOT, AND, OR, or XOR). Notice that the NOT logical operator does not use word B. It only operates on word A. Now let's look at the computer's "Arithmetic Unit" as illustrated in the "AU.LG" sample circuit. Word A is on the right directly connected to the Add unit and is represented by the fixed values FALSE, TRUE, FALSE, TRUE or 0101 binary. Word B is on the left and is represented by the fixed values FALSE, FALSE, TRUE, TRUE or 0011 binary. The "Carry-In" input is represented by the FALSE value or zero binary in the upper left portion of the circuit. This circuit also has three input switches: enable and two selector switches. The enable switch is on the far right. The switch in the middle selects between addition and subtraction. When this switch is FALSE, it is selecting addition, and when it is TRUE it is selecting subtraction. When the switch on the bottom left is set to TRUE word B is set to 0001 (one) and the carry-in bit is set to zero. Under this configuration the circuit implements the increment or decrement instruction as determined by the value of the middle switch. Next we will look at the "ALU.LG" sample circuit. This circuit illustrates the combined Arithmetic and Logic circuits described above and is referred to as the "Arithmetic Logic Unit" or ALU. This circuit has four input switches: three are used to select one of the eight operations to be performed (ADD, SUB, INC, DEC, NOT, AND, OR, and XOR) and the last switch is used to enable or disable the output. The enable switch is located closest to the top of the screen. The switch located on the left selects between the Arithmetic Unit (when FALSE) and the Logic Unit (when TRUE). The remaining two switches select the individual operations of these units. The FALSE fixed node toward the top of the screen represents the value zero for the carry-in data. The next four fixed values (TRUE, FALSE, TRUE, FALSE) represent word A, but because these values are ordered least significant bit to most significant bit, they represent the binary value 0101. Word B is represented by the bottom four fixed values (TRUE, TRUE, FALSE, FALSE) or 0011 binary. The following table identifies the results of the eight possible operations: Notice the circuit organizes the input and output data least significant bit to most significant bit which is in reverse order as written in the table. ╔═════════╦═════╤══════════╤════════╗ ║S2 S1 S0 ║ Opr.│ Equation │ Output ║ ╠═════════╬═════╪══════════╪════════╣ ║ 0 0 0 ║ ADD │ A + B │ 1000 ║ ║ 0 0 1 ║ INC │ A + 1 │ 0110 ║ ║ 0 1 0 ║ SUB │ A - B │ 0010 ║ ║ 0 1 1 ║ DEC │ A - 1 │ 0100 ║ ║ 1 0 0 ║ NOT │ NOT A │ 1010 ║ ║ 1 0 1 ║ OR │ A OR B │ 0111 ║ ║ 1 1 0 ║ AND │ A AND B │ 0001 ║ ║ 1 1 1 ║ XOR │ A XOR B │ 0110 ║ ╚═════════╩═════╧══════════╧════════╝ where: S2, S1, and S0 are the selector switches from left to right. The ALU is the brain of the computer. It performs all the integer calculations. Most computers have additional instructions in their ALU, such as multiply and divide. The floating point instructions are normally performed by a separate unit called the "Floating Point Unit" or FPU. If we look at the Intel family of microprocessors we find the original 8088, 286, and 386 contained the ALU and the 8087, 287, and 387 contained the corresponding FPU. The 486 (DX, DX2, and DX4 models) was the first Intel microprocessor to contain an ALU and an FPU. The Pentium microprocessor actually contains two ALUs and one FPU. The next logical step is to build the "Central Processing Unit" or CPU. However, this requires additional circuits to access memory, decode instructions, and provide registers for results stored within the CPU. Due to the limitation of the screen being too small, we are not able to generate a sample CPU circuit. Instead I will only discuss some common functions of a CPU. Let's start by looking at the different types of instructions the CPU processes. The first family of instructions I will discuss is the Move instruction, which is normally abbreviated "MOV." The move instruction moves data between the Random Access Memory (RAM) and the CPU registers. Also, if the CPU has multiple registers, it can move data between the registers within the CPU. There are other variations on the move instruction including the Move- Immediate which loads the next piece of data in the instruction stream as data instead of an address pointing to the data. Besides storing data in registers, the CPU keeps track of the state of each calculations in a special register called the "Flag-Register." Each bit in the flag-register represents a different state and is called a "flag." As an example, if you look closely at the ALU sample circuit, you will see both the LU and AU unit have two additional outputs labeled "c" and "z." These are the carry-out flag and zero flag bits that are set as a result of the calculation performed. The AU sets the carry-out flag any time the carry-out bit is set. Both the AU and the LU set the zero flag any time all four bits of the output are set to zero. The carry-out flag can be used as an input to the next calculation for calculating values larger than the normal width of the word, in our case 4-bits. The zero flag can be used by other instructions for performing conditional operations depending on the results of the calculation. Most computers have a "Jump," abbreviated "JMP," and conditional jump instruction. These instructions are used to implement the IF-THEN-ELSE instructions normally found in most high level languages. Another example of using a conditional jump instruction would be a loop that decrements a counter. The last instruction in the loop might be "Jump to top of the loop if counter is not zero." As long as the counter is not zero, the loop will continue to be processed. Of course, you must decrement the counter somewhere in the loop, otherwise the program would never leave this loop. Another very important family of instructions is the "Call" and "Return" instructions. These instructions are used to support subroutines and functions. When a computer calls a subroutine, it places the address of the instruction following the call instruction in a piece of memory called the stack. When the subroutine completes, it executes the return instruction that jumps back to the address stored in the stack. A stack is a portion of normal RAM set aside just for calling subroutines. The CPU keeps two pointer registers. The first one is used to point to the instructions and the other points to the stack. Normally, a high level language will use a series of PUSH instructions to save the registers on the stack and use the POP instruction to restore these registers to their original value when returning from the subroutine. Also, the PUSH and POP instructions can be used to pass parameters to the subroutine. MEMORY A computer can have several types of memory. Memory can be separated into two categories: "Read Only Memory" or ROM, and "Random Access Memory" or RAM. These categories can be further subdivided either by type or by function. ROM is permanent memory that cannot be changed and retains its value when the computer is powered off. Functionally, ROMs contain instructions used to start the computer and interface with the hardware of the computer. There are system ROMs, video ROMs, Disk controller ROMs, etc. These types of ROMs function as Basic Input and Output System (BIOS) allowing the software programs to access the hardware without knowing the details of the hardware installed. Originally an ROM implied a circuit that had its software programs (instructions) etched in. Today, there are Programmable ROMs (PROM) that start with a generic circuit with little fuses that can be one time blown in a pattern representing the software program. Also, there is an Erasable PROM (EPROM) that can be programmed using special equipment and erased by shining ultraviolet light on the chip. The latest technology, called Flash PROM, can be programmed by the computer without using special equipment. Just like there are several types and functions of ROMs, there are several types and functions of RAM. In general, RAM is used to store instructions and data that the CPU processes. Software programs can be read from disk and loaded into RAM. Once in RAM, the CPU can process the instructions contained in the software program. When it needs to load another software program, it can overwrite the first software program since it is no longer needed and can be loaded from disk the next time it is executed. Some hardware, like the video adapter, also contains RAM. This RAM is used to contain the images that are being displayed on the monitor. RAM can be categorized into two types: Static RAM and Dynamic RAM. Static RAM is faster, larger, cost more, and uses more power than Dynamic RAM. Static RAM can be constructed from logic gates. The CPU register described above is a type of static RAM. Dynamic RAM uses a 2-dimensional matrix of small capacitors etched into the silicon chip to store information. Like most capacitors, they will gradually lose their charge and eventually forget the information stored in them. Consequently, dynamic RAM must be refreshed several thousand times per second. There is special circuitry external to the CPU that periodically instructs the dynamic RAM to read and write back one row of memory to refresh the values stored in the capacitors. By working on one row at a time, a Megabyte (a million bytes) of RAM can be fully refreshed with only one thousand accesses instead of a million accesses. The number of accesses required to fully refresh dynamic RAM is the square root of the chip size. As an example, a 4- Mbit chip requires 2,048 accesses, a 16-Mbit chip requires 4,096 accesses to fully refresh the chip. The last type of RAM I will discuss is called "Cache." In computer terms, a cache is a small but fast static memory located between the CPU and the slower dynamic RAM. The cache stores the most recently accessed memory in anticipation that the computer will need it again. As an example, if the CPU is processing a loop in a software program, the instructions in the loop will be accessed over and over again until it exits the loop. Since the dynamic RAM is several times slower than the CPU, a cache can be used to speed up the performance. Now, let's look at the "DATA.LG" sample circuit. This circuit is a static RAM example of a single 4-bit word. Each bit is a data latch as described earlier. The switch on the lower right clears (zero) memory when it is FALSE. The switch in the upper left is the enable switch. It sets memory to the values on the input when it is FALSE. Both switches should not be set to FALSE simultaneously. When both switches are TRUE, the RAM remembers the last setting and ignores the input. For illustrative purposes, the input is preset to TRUE, FALSE, TRUE, and FALSE. Let's look at the "RAM.LG" sample circuit. This circuit combines four 4-bit static RAM words into a single circuit. Each of the 4-bit static RAM modules is configured as illustrated in the "DATA.LG" sample circuit. When the top switch is FALSE, the 3-state devices are active and output the contents of the memory. The next switch down is the write switch. When it is set to FALSE, the input data is set to the selected RAM module. Notice the input data is preset to TRUE, FALSE, TRUE, FALSE. The next two switches select which of the four RAM modules is accessed. The last switch on the bottom is the clear switch. When it is set to FALSE, all four RAM modules are cleared. It should be set TRUE during normal operations. This concludes the discussion on computer circuits. I hope you now have a better understanding of the fundamental logic circuits that comprise a computer. INTEGRATED CIRCUITS (IC) An "Integrated Circuit" (IC) is a single piece of semiconductor material containing multiple electronic components. The original ICs only contained a few components, possibly a single logic gate. As the technology improved, the components became smaller, and more gates were placed on a single chip. Using today's technology, over a million transistors can be placed on a single IC chip representing hundreds of thousands of logic gates. In the Logic Circuit Analysis program, the term "Integrated Circuit" (IC) takes on a slightly different meaning. The Logic Circuit Analysis library contains both basic logic gates and Integrated Circuits (like Flip-Flops, Counters, 4-bit ALU and 4-bit multiply circuit), which are circuits created using the Logic Circuit Analysis program, saved in a file with the "LGL" extension, and referenced in the library. The "LOGIC.LGL" file contains all the parameters and screen locations for each item in the library. (See the section below that describes this file format). Each IC is stored in a separate file. As an example, the Exclusive OR gate is stored in the file "XOR.LGL" located in the LGL subdirectory. You can view this circuit by changing to the LGL subdirectory in the Select Sample Circuit menu. From the Directories menu select the ".." item to move up one directory. Select the "LGL" item to display the library circuits. From the Circuits menu select "XOR.LGL." You will notice that there are no switches for input. The first nodes created correspond to the connection points. By convention, the connection order is inputs followed by outputs. LGL files are not always easy to read, since they use the fewest number of nodes necessary for the library. Nodes can be moved around on the screen, but if you delete one of the connection nodes, you cannot simply recreate it. Since the order in which the nodes were created is essential to maintain compatibility with the "LOGIC.LGL" file. Please do not modify the LGL library files. USER DEFINED ICs Why did I discuss LGL files? Because you can create your own circuits and add them to the library. The last eight icons on the second page of the library are reserved for your use. They are stored in the files LGL\USER1.LGL through LGL\USER8.LGL. The connection nodes are already created and organized on the screen in a pattern matching the icon connection points. All you have to do is add your circuits to these files. You can embed other ICs into your circuit, the only limitation is the 1,000 total logic gates which includes the logic gates within each IC and the IC icon itself. You can move the nodes around the screen, but please do not delete them. If you make a mistake in your user defined IC file, you can start all over by copying the LGL\USER.LGL file into the file you were working on. This file provides a good starting point. Please do not modify the LGL\USER.LGL file. I hope you enjoyed this tutorial and will continue to use this program to explore other logic circuits. This program allows you to try some circuits without actually building the circuit. SPECIFICATIONS REQUIREMENTS ──────────── IBM-PC or compatible with 286 or later microprocessor 1 MB of disk space 300 KB minimum available RAM, (after DOS, drivers and TSR) 400 KB maximum available RAM required for complex circuits and no EMS EGA or VGA graphics adapter with 256 KB of RAM installed Color Monitor SUPPORTS (but not required) ─────────────────────────── Mouse (2 or 3 button) with MOUSE.SYS or MOUSE.COM device driver. Expanded Memory (EMS). It will use 64 KB of EMS if available. DOS ENVIRONMENTAL VARIABLES ─────────────────────────── TMP Sets location of LOGIC.PCX and LOGIC.LG file, otherwise written to the default directory. Example: SET TMP=D:\ MONITOR Can be set to EGA or VGA. The program will automatically detect if an EGA or VGA adapter is installed. The MONITOR variable will override the automatic detection. Example: SET MONITOR=EGA EMS Can be set to OFF or NO to override auto-detection so not to use EMS memory even if it is available. Example: SET EMS=OFF PROGRAM LIMITS ────────────── 112 Library Entries 1,000 Logic Gates per circuit, including ICs and their logic gates 3,000 Nodes per circuit 7,000 Connections per circuit 20 Connection terminals per IC 8 Connections per node. 8 User Definable CircuitsSUMMARY OF KEYS OPENING MENU Cursor Keys - Highlight the desired item HOME - Highlight "Analyze Circuit" END - Highlight "Save and Exit" ENTER - Select the highlighted item SELECT SAMPLE CIRCUIT MENU PGUP, PGDN - Display additional pages of sample circuits Cursor Keys - Highlight the desired sample circuit HOME - Highlight the first sample circuit on this page END - Highlight the last sample circuit on this page ENTER - Select the highlighted sample circuit ESC, F10 - Exit this menu without selecting a sample circuit ANALYZE CIRCUIT F1 - Identify number of Gates, Nodes, and Connections Second F1 - Full screen help F5 - Online Tutorial (Tutor) F6 - Modify Circuit (Edit) LEFT and RIGHT - Highlight Switch or Clock UP or HOME - Set switch to up position DOWN or END - Set switch to down position ENTER - Toggle Switch + - Speed up the rate the screen is updated - - Slow down the rate the screen is updated PGDN - Speed up the clock rate PGUP - Slow down the clock rate w - Save screen into PC Paintbrush compatible file F10, ESC - Exit MODIFY CIRCUIT F1 - Brief help Second F1 - Full screen help F2 - Redraw screen F3 - Move a logic gate (Node or IC) F4 - Access Library of Components F5 - Online Tutorial (Tutor) F6 - Analyze Circuit (Calc) Cursor Keys - Move Cursor CTRL-BACKSPACE - Delete logic gate (Node or IC) ENTER - Make a Connection, or Lock it in position F10, ESC - Exit LIBRARY OF COMPONENTS F1 - Help (Second F1 for full screen help) Cursor Keys - Highlight logic gate (Node or IC) PGUP, PGDN - Switch Pages of Library Components ENTER - Select Logic Gate or IC F10, ESC - Exit LIBRARY The Library is based on the AND, OR, NAND, and NOR logic gates. Each logic gate can contain between one and four inputs. ICs are circuits created using the Logic Circuit Analysis program and made available in the library. The Library contains the following items: Type Description ───── ─────────────────────────────────────────────── INODE Interconnect Node VNODE TRUE Node VNODE FALSE Node SNODE Switch Node CLOCK Clock Node IC Reserved 3WAY 3-State Gate NOR NOT Gate (1-In NOR Gate) AND 2-In AND Gate AND 3-In AND Gate OR 2-In OR Gate OR 3-In OR Gate NAND 2-In NAND Gate NAND 3-In NAND Gate NOR 2-In NOR Gate NOR 3-In NOR Gate AND 4-In AND Gate OR 4-In OR Gate NAND 4-In NAND Gate NOR 4-In NOR Gate IC Integrated Circuit: XOR.LGL, 2-In Exclusive OR IC Integrated Circuit: XNOR.LGL, 2-In Exclusive NOR IC Integrated Circuit: SRLatch.LGL, Set-Reset Latch IC Integrated Circuit: DLatch.LGL, Data Latch IC Integrated Circuit: SRFF.LGL, Set-Reset Flip-Flop IC Integrated Circuit: DFF.LGL, Data Flip-Flop IC Integrated Circuit: DFFsc.LGL, Data Flip-Flop, Preset and Clear IC Integrated Circuit: JKFFsc.LGL, J-K Flip-Flop, Preset and Clear IC Integrated Circuit: FullAdd.LGL, 1-bit Full Adder IC Integrated Circuit: Add4.LGL, 4-bit Adder IC Integrated Circuit: Counter.LGL, 4-bit Asynchronous Counter IC Integrated Circuit: LScount.LGL, 4-bit Synchronous Counter with Load IC Integrated Circuit: 3state.LGL, 4-bit 3-State Gate IC Integrated Circuit: Data.LGL, 4-bit Data Latch IC Integrated Circuit: 2to4.LGL, 2 to 4 Line Decoder IC Integrated Circuit: 3to8.LGL, 3 to 8 Line Decoder IC Integrated Circuit: LU.LGL, 4-bit Logic Unit IC Integrated Circuit: AU.LGL, 4-bit Arithmetic Unit IC Integrated Circuit: ALU.LGL, 4-bit Arithmetic Logic Unit IC Integrated Circuit: Multiply.LGL, 4-bit MultiplyIC Integrated Circuit: ANDgate.LGL, 4-bit AND gate IC Integrated Circuit: SRFFsc.LGL, Set-Reset Flip-Flop, Preset & Clear IC Integrated Circuit: ShiftReg.LGL, 4-bit Shift Register IC Integrated Circuit: AorB.LGL, 4-bit 1 of 2 word selector IC Integrated Circuit: 2Xbar.LGL, 2-line Cross Bar switch IC Integrated Circuit: 4Xbar.LGL, 4-line Cross Bar switch IC Integrated Circuit: User.LGL, Reserved IC Integrated Circuit: Divide.LGL, 4-bit Divide IC Integrated Circuit: ECLNOT.LGL, ECL-Type NOT Gate IC Integrated Circuit: 2AndNand.LGL, ECL-Type 2-In AND-NAND Gate IC Integrated Circuit: 3AndNand.LGL, ECL-Type 3-In AND-NAND Gate IC Integrated Circuit: 4AndNand.LGL, ECL-Type 4-In AND-NAND Gate IC Integrated Circuit: 2OrNor.LGL, ECL-Type 2-In OR-NOR Gate IC Integrated Circuit: 3OrNor.LGL, ECL-Type 3-In OR-NOR Gate IC Integrated Circuit: 4OrNor.LGL, ECL-Type 4-In OR-NOR Gate IC Integrated Circuit: XorXnor.LGL, ECL-Type 2-In Exclusive OR-NOR Gate . . . IC Integrated Circuit: User1.LGL, User Defined IC IC Integrated Circuit: User2.LGL, User Defined IC IC Integrated Circuit: User3.LGL, User Defined IC IC Integrated Circuit: User4.LGL, User Defined IC IC Integrated Circuit: User5.LGL, User Defined IC IC Integrated Circuit: User6.LGL, User Defined IC IC Integrated Circuit: User7.LGL, User Defined IC IC Integrated Circuit: User8.LGL, User Defined IC SAMPLE CIRCUITS The following examples can be found in the \LOGIC\LG sub-directory: Filename Description ─────────── ─────────────────────────────────────────────── 16XBAR.LG 16-line Cross Bar Switch 1OF2.LG 1 of 2-line Selector 1OF4.LG 1 of 4-line Selector 2TO4.LG 2-bit to 4-line Decoder 2XBAR.LG 2-line Cross Bar Switch 3STATE.LG 3-State Gate 3TO8.LG 3-bit to 8-line Decoder 4BITADD.LG 4-bit Addition 4BITSUB.LG 4-bit Subtraction 4TO2.LG 4-line to 2-bit Encoder 4XBAR.LG 4-line Cross Bar Switch ALU.LG 4-bit Arithmetic Logic Unit AORB.LG 4-bit wide 1 of 2-line Selector AU.LG 4-bit Arithmetic Unit CLOCK.LG Clock formed by three NOT Gates COUNTER.LG 4-bit Asynchronous Counter DATA.LG 4-bit word Static RAM DEMORGAN.LG DeMorgan's Theorem Example DFF.LG Data Flip-Flop DFFSC.LG Data Flip-Flop with Preset and Clear DLATCH.LG Data Latch FPMULTP.LG 8-bit Floating Point Multiplier FULLADD.LG Full Adder HALFADD.LG Half Adder JKFFSC.LG J-K Flip-Flop with Preset and Clear LSCOUNT.LG 4-bit Synchronous Counter with Parallel input LU.LG 4-bit Logic Unit MULTIPLY.LG 4-bit Multiplier NANDLOGC.LG Logic Gates from only NAND Gates NANDNOR.LG NAND and NOR Gates NORLOGIC.LG Logic Gates from only NOR Gates RAM.LG 4-word by 4-bit Static RAM REGISTER.LG 4-bit Register SHIFTREG.LG 4-bit Shift Register with Serial or Parallel input SPSHREG.LG 4-bit Shift Register with Serial input SRFF.LG Set-Reset Flip-Flop SRFFSC.LG Set-Reset Flip-Flop with Preset and Clear SRLATCH.LG Set-Reset Latch SRLATCHE.LG Set-Reset Latch with Enable SYNCOUNT.LG 4-bit Synchronous Counter UDCOUNT.LG 4-bit Up or Down Synchronous Counter XOR.LG Exclusive OR Gate LOGIC.LGL FILE FORMAT LOGIC.LGL contains the specifications for each library entry. There is one line for each entry as follows: TYPE NL NC NP --- Locations x y --- --- Parameters --- where TYPE is: INODE - Interconnect Node VNODE - Fixed Value Node SNODE - Switch Node CLOCK - Clock or Pulse Node 3WAY - 3-State Logic Gate AND - Logical AND OR - Logical OR NAND - Logical NAND (NOT AND) NOR - Logical NOR (NOT OR) IC - Integrated Circuit - Logic circuit made from above logic gates and stored in separate files NL: Number of Locations NC: Number of Connections must be less then or equal to NL NP: Number of Parameters --- Locations x y --- Locations specified in x y pairs relative to upper left corner of icon. The first NC locations are the connections, any additional locations are for Resistor current, Potentiometer % turns, or INODE Voltage labels. --- Parameters --- The number and type of parameters depends on the TYPE as follows: TYPE NL NC NP Locations Parameters ───── ── ── ── ─────────────────────────── ─────────────────────────── INODE 1 1 0 connection VNODE 1 1 1 connection Logical Value 0 or 1 SNODE 1 1 0 connection CLOCK 1 1 0 connection 3WAY 3 3 0 input, enable, output AND ? ? 0 inputs, output OR ? ? 0 inputs, output NAND ? ? 0 inputs, output NOR ? ? 0 inputs, output IC ? ? -1 inputs, outputs FILENAME.LGL Up to 20 Connections The Library are based on the following Logic Gates: AND, OR, NAND and NOR can have from 1 to 4 inputs, but only one output. A NOT is a single input NOR (or NAND). ICs are all predefined Logic Circuits that may contain other ICs. Integrated Circuits (ICs) files are stored in the \LOGIC\LGL sub-directory. ICs are all predefined Logic Circuits that contain Logic Gates or other ICs. LG AND LGL FILE FORMATS Files with the extension "LG" are sample circuit files located in the LG sub- directory. Files with the extension "LGL" are library (IC) circuit files located in the LGL sub-directory. Both files contains circuit created by the Logic Circuit Analysis program, and have the same format: The first line contains two numbers as follows: NG NN where NG = Number of Logic Gates or ICs NN = Number of Nodes (Interconnect, Fixed, Switch, or Clock) The next NG lines contains the logic gates one per line as follows: LIB ROW COL N N1 N2 ... where LIB = Library entry (0-111) ROW = Screen row location of icon (0-299) COL = Screen column location of icon (0-79) N = Number of connection terminals N1, N2, ... = Node corresponding to each connection Nodes are numbered starting with 1000 The next NN lines contains the nodes, one per line as follows: LIB ROW COL N G1 C1 G2 C2 where LIB = Library entry (0-111) ROW = Screen row location of icon (0-299) COL = Screen column location of icon (0-79) N = Number of connections G1, G2, ... = Logic Gate (0-999), or Node C1, C2, ... = Connection on logic gate or Node G1, G2, ...